package com.leetcode.August;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description: 15. 三数之和
 *要找到和为0且不重复的三元组，首先需要对数组nums进行从小到大排序。对于排序后的数组nums，i从0开始进行循环，对于每一轮循环，j初始为i+1，k初始为nums.size()-1，
 * 当nums[i] + nums[j] + nums[k] < 0时，即将j向右移动，增大nums[j]，使三元组和增大；而当nums[i] + nums[j] + nums[k] > 0时，即将k向左移动，减小nums[k]，使三元组和减小，直至等于0，记录此时的三元组。
 *
 * 上述方法能够找到所有符合条件的三元组，但得到的三元组有些是重复的，因此在代码中需要提前加入条件避免录入重复的三元组。已知当有i，j，k符合nums[i] + nums[j] + nums[k] = 0时，
 * 倘若下一次循环的nums[i+1]与此时nums[i]的大小相等，则必然会出现重复的三元组，j也同理，因此当发现重复后，需要向右移动直至找到下一个不重复的值。当避免nums[i]和nums[j]重复后，所记录得到的三元组就都是不同的
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-17 21:18
 */
public class LC15三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    while (j < k && nums[j] == nums[j - 1]) j++;
                } else if (sum < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return ans;
    }
}
